package com.company.ljh.medium;

import com.company.ljh.utils.TreeNode;

import java.util.HashMap;

/**
 * @description:
 * 1448. 统计二叉树中好节点的数目
 * 提示
 * 中等
 * 90
 * 相关企业
 * 给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
 *
 * 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/4 16:11
 * @version:1.0
 */
public class 统计二叉树中好节点的数目 {

    public int goodNodes(TreeNode root) {
        return traversalTree(root,Integer.MIN_VALUE);
    }
    //遍历时保存当前路径下的最大值，并返回由该节点开始的好节点数量
    public int traversalTree(TreeNode node,int max){
        if(node == null){
            return 0;
        }
        int size = 0;
        if(node.val >= max){
            max = node.val;
            size ++;
        }
        int leftDepth = traversalTree(node.left,max);
        int rightDepth = traversalTree(node.right,max);
        return leftDepth+rightDepth+size;
    }
}
